package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 135. 分发糖果
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/10 21:33
 */
public class Candy {

    public static void main(String[] args) {
        Candy test = new Candy();

        // 5
//        int[] arr = {1, 0, 2};

        // 4
//        int[] arr = {1, 2, 2};

        // 28
//        int[] arr = {32, 22, 22, 35, 0, 13, 22, 35, 19, 12, 23, 18, 37, 13, 35, 18};

        // 9
//        int[] arr = {38, 22, 22, 10, 7};

        int[] arr = Utils.getArr(20000, 0, 20000);
//        int[] arr = Utils.getArr(10000, 0, 10000);

        int candy = test.candy(arr);
        System.out.println(candy);

    }

    public int candy(int[] ratings) {


//        int m = Integer.MAX_VALUE;
//
//        for (int rating : ratings) {
//            m = Math.min(m, rating);
//        }
//        System.out.println(m);
//
//        Map<Integer, Integer> map = new HashMap<>();
//
//
//        int length = ratings.length;
//        int[] tt = new int[length];
//
//        for (int i = 0; i < length; i++) {
//            tt[i] = ratings[i];
//        }
//
//        Arrays.sort(tt);
//
//        for (int i = 0; i < length; i++) {
//            map.put(tt[i], i);
//        }
//
//        for (int i = 0; i < length; i++) {
//            ratings[i] = map.get(ratings[i]);
//        }
//        System.out.println(Arrays.toString(ratings));

        int sum = 0;
        int count = 0;
        int last = -1;
        int item = 0;
        int lastMax = -1;
        for (int rating : ratings) {
            if (rating > last) {
                item++;
                sum += item;
                count = 0;
                lastMax = item;
            } else if (rating == last) {
                count = 1;
                item = 1;
                sum += count;
                lastMax = Integer.MAX_VALUE;
            } else {
                item = 1;
                if (lastMax == count + 1) {
                    count++;
                }
                count++;
                sum += count;
            }
            last = rating;
        }
        return sum;
    }

}
